<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>popot-2.01: POPulation based Optimization Toolbox</title>

<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />

<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>

</head>
<body>
<div id="top"><!-- do not remove this div! -->


<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  
  
  <td style="padding-left: 0.5em;">
   <div id="projectname">popot-2.01
   
   </div>
   
  </td>
  
  
  
 </tr>
 </tbody>
</table>
</div>

<!-- Generated by Doxygen 1.7.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li class="current"><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li><a href="examples.html"><span>Examples</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">POPulation based Optimization Toolbox </div>  </div>
</div>
<div class="contents">
<div class="textblock"><p>NOT YET UPDATED !!!!!! The 2.0 version introduces major modifications in the way to use the library</p>
<h2><a class="anchor" id="intro_sec"></a>
Introduction</h2>
<p>In this toolbox, you will find various black box optimization algorithms, namely :</p>
<ul>
<li>Particle Swarm Optimization (with some of its variants), see Engelbrecht</li>
<li>... more to come</li>
</ul>
<h3><a class="anchor" id="pso_sec"></a>
Particle Swarm Optimization</h3>
<p>Generally speaking, a particle swarm algorithm works by spreading a set of particles in a search space and by moving these particles according to certain rules. The traditional update rules, as defined by Kennedy, involve linear update of the positions and velocities. The update of the velocity depends on the velocity itself (with an inertia factor), on the difference between the best position the particle ever had and its current position (this is called the cognitive component), and the difference between the best position that particles in the neighborhood of the updated particle ever had and its current position (this is called the social component). Different variations have been introduced but the basic concept remains the same.<br/>
</p>
<p>In the implementation of this library, a swarm is a parametrized object. It can be parametrized by numerical parameters (such as cognitive or social factors) the type of particle, the type of neighborhood, etc... and the problem to solve. The algorithms are defined here as <b>minimization algorithms</b>. Therefore, the problem (see <a class="el" href="namespacepopot_1_1problems.html">popot::problems</a> namespace for example) provides a function to minimize.</p>
<p>Generally, to use the library you need to define :</p>
<ul>
<li>A problem (see e.g. <a class="el" href="namespacepopot_1_1problems.html">popot::problems</a>) which provides a function to minimize</li>
<li>A particle type (see e.g. <a class="el" href="namespacepopot_1_1PSO_1_1particle.html">popot::PSO::particle</a>) which takes a problem as a parameter and some parameters (for example the cognitive and social factors)</li>
<li>A topology (see e.g. <a class="el" href="namespacepopot_1_1PSO_1_1topology.html">popot::PSO::topology</a>) which defines the network through which the particles communicate</li>
<li>An algorithm (see e.g. <a class="el" href="namespacepopot_1_1PSO_1_1algorithm.html">popot::PSO::algorithm</a>) which defines the different steps to update the state of the particles. It requires a particle type, a toplogy and a stopping criteria</li>
</ul>
<p>However, there are already some standard versions of PSO implemented : SPSO2011 and SPSO2006 </p>
<h2><a class="anchor" id="sec_problems"></a>
Problems</h2>
<p>Different benchmark problems are already coded in the <a class="el" href="namespacepopot_1_1problems.html">popot::problems</a> namespace :</p>
<ul>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Ackley.html" title=" Bounds [-30; 30]">popot::problems::Ackley</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Griewank.html" title=" Bounds [-600;600]">popot::problems::Griewank</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Sphere.html" title=" Bounds [-100;100]">popot::problems::Sphere</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1QuarticNoise.html" title="  , Bounds [-1.28,1.28]">popot::problems::QuarticNoise</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Rastrigin.html" title=" Bounds [-5.12,5.12]">popot::problems::Rastrigin</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Rosenbrock.html" title=" with  Bounds [-30,30]">popot::problems::Rosenbrock</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Schwefel1__2.html" title=" Bounds [-500,500]">popot::problems::Schwefel1_2</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Schwefel.html" title=" Bounds [-500,500]">popot::problems::Schwefel</a> function</li>
<li>N-dimensional <a class="el" href="classpopot_1_1problems_1_1Salomon.html" title=" Bounds [-600,600]">popot::problems::Salomon</a> function</li>
<li>2 dimensional <a class="el" href="classpopot_1_1problems_1_1Dropwave.html" title=" Bounds [-100,100]">popot::problems::Dropwave</a> function</li>
<li>....</li>
</ul>
<p>You can obviously define your own problem. Just check problem.h and the examples to see how one can define its own custom problem.</p>
<h2><a class="anchor" id="sec_particles"></a>
Particle types</h2>
<p>Different particles are defined, provided in the <a class="el" href="namespacepopot_1_1PSO_1_1particle.html">popot::PSO::particle</a> namespace :</p>
<ul>
<li>Standard particle 2006 : popot::PSO::particle::SPSO2006Particle</li>
<li>Standard particle 2011 : popot::PSO::particle::SPSO2011Particle</li>
<li>Barebone particle : popot::PSO::particle::BareboneParticle</li>
<li>Modified barebone particle : popot::PSO::particle::ModifiedBareboneParticle</li>
</ul>
<h3><a class="anchor" id="non_stochastic_traditional_particle"></a>
Non stochastic traditional particle</h3>
<p>This standard PSO relies on the following particle's position and velocity update :<br/>
 </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\begin{eqnarray*} v_{k+1} &amp;=&amp; w v_k + c_1 * R_1^T (p^l - p_k) + c_2 * R_2^T (p^g - p_k) \\ p_{k+1} &amp;=&amp; p_k + v_{k+1} \\ &amp;\mbox{with}&amp; v_k, p_k \in R^N \end{eqnarray*}" src="form_0.png"/>
</p>
<p> where <img class="formulaInl" alt="$R_1, R_2$" src="form_1.png"/> are N-dimensional vectors with uniformely distributed random values in [0;1]</p>
<p>The particles can be updated synchronously or asynchronously.</p>
<h3><a class="anchor" id="traditional_particle"></a>
Traditional particle</h3>
<p>This particle uses the same update rules as the previous particle type except that we reevaluate the fitness of the best position before update the best position. This is usefull in case the fitness is stochastic.</p>
<h3><a class="anchor" id="barebone_particle"></a>
Barebone particle</h3>
<p>later....</p>
<h3><a class="anchor" id="modified_barebone_particle"></a>
Modified barebone particle</h3>
<p>later ...</p>
<h2><a class="anchor" id="sec_topologies"></a>
Topologies</h2>
<p>The particles communicate with the particles within their neighborhood. The neighborhood is used to define who informs whom, involved in updating the velocity of the particles. Different topologies are implemented :</p>
<ul>
<li>Full connectivity (popot::PSO::topology::Full) : the best swarm's position, for each particle, is computed within the <img class="formulaInl" alt="$N$" src="form_2.png"/> other particles</li>
<li>Ring connectivity (popot::PSO::topology::Ring) : the best swarm's position, for each particle, is computed within the 2 closest neighbours (left and right) and the best position of the particle itself</li>
<li>VonNeuman (popot::PSO::topology::VonNeuman): the best swarm's position, for each particle, is computed within the 4 closest neighboors (north, east, west, south) and itself. The particles are somehow placed on a 2D grid.</li>
<li>RandomInformants (popot::PSO::topology::RandomInformants) each particle informs K other particles</li>
<li>Probabilistic informants (popot::PSO::topology::AdaptiveRandom) : each particle informs each other particle with a given probability</li>
</ul>
<p>Each particle hosts a <a class="el" href="classpopot_1_1PSO_1_1neighborhood_1_1Neighborhood.html" title="A neighborhood contains a vector of particles belonging to the neighborhood as well as a pointer (not...">popot::PSO::neighborhood::Neighborhood</a> which is set from the defined topology. A neighborhood can be recomputed for e.g. when there is no improvement of the best position ever found by the algorithm.</p>
<p>Shown below are illustrations of three topologies for a swarm with 9 particles (see example-002.cc).</p>
<div class="image">
<img src="graph_full.png" alt="graph_full.png"/>
<div class="caption">
Full connectivity</div></div>
 <div class="image">
<img src="graph_ring.png" alt="graph_ring.png"/>
<div class="caption">
Ring connectivity</div></div>
 <div class="image">
<img src="graph_vonneuman.png" alt="graph_vonneuman.png"/>
<div class="caption">
VonNeuman connectivity</div></div>
 <h2><a class="anchor" id="sec_algorithms"></a>
Algorithms</h2>
<p>So far, a single algorithm is implemented, see <a class="el" href="classpopot_1_1PSO_1_1algorithm_1_1Base.html">popot::PSO::algorithm::Base</a> .</p>
<h2><a class="anchor" id="papers_sec"></a>
Some relevant papers</h2>
<ul>
<li>Shi, Y. H., Eberhart, R. C., (1998).<b>Parameter Selection in Particle Swarm Optimization</b> , The 7th Annual Conference on Evolutionary Programming, San Diego, USA. (introduced the inertia factor)</li>
<li>Kennedy, J. and Mendes, R. (2002). <b>Population Structure and Particle Swarm Performance</b></li>
<li>Clerc, M. , Kennedy J. (2002) <b> The Particle Swarm—Explosion, Stability, and Convergence in a Multidimensional Complex Space</b>.</li>
<li>M.E.H. Pedersen (2010), <b>Good Parameters for Particle Swarm Optimization</b>,<em>Technical Report no. HL1001</em></li>
<li>A. Engelbrecht (2010), <b>Heterogeneous Particle Swarm Optimization</b>, <em>ANTS 2010, LNCS 6234</em>, pp 191-202</li>
<li>A. Engelbrecht (2010), <b>Fundamentals of computational swarm intelligence</b>, Wiley. </li>
</ul>
</div></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Defines</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>



<hr class="footer"/><address class="footer"><small>
Generated by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.7.5
</small></address>

</body>
</html>
